package nowCoder;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * 将路径数组变为统计数组
 * 输入：代表一张图的数组paths
 * 将paths数组变为距离数组numArr
 */
public class 路径数组到统计数组 {
    public void pathArrToNumArr(int[] paths) {
        HashMap<Integer, Integer> rst = new HashMap<Integer, Integer>();
        for (int i = 0; i < paths.length; i++) {
            int sum = 0;
            int a = i, b = paths[i];
            while (true) {
                if (a < i) {
                    sum += paths[a];
                    break;
                } else {
                    if(a!=b){
                        sum++;
                        a = b;
                        b = paths[b];
                    } else
                        break;
                }
            }
            paths[i] = sum;
            if(rst.containsKey(sum)){
                rst.put(sum,1+rst.get(sum));
            } else{
                rst.put(sum,1);
            }

        }
        for(int i=0;i<paths.length;i++)
            paths[i] = 0;
        Set<Map.Entry<Integer, Integer>> entrySet = rst.entrySet();
        for(Map.Entry<Integer, Integer> entry:entrySet){
            paths[entry.getKey()] = entry.getValue();
        }
    }


    public static void main(String[] args) {
        路径数组到统计数组 ll = new 路径数组到统计数组();
        int[] paths = {9,1,4,9,0,4,8,9,0,1};
        ll.pathArrToNumArr(paths);
        for(int a:paths)
            System.out.println(a+" ");
    }
}
